/*
 * Created on Jul 6, 2007
 *
 * Copyright (c) 2007, the JUNG Project and the Regents of the University 
 * of California
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * http://jung.sourceforge.net/license.txt for a description.
 */
package edu.uci.ics.jung.algorithms.scoring;

import java.util.HashMap;
import java.util.Map;

import org.apache.commons.collections15.Transformer;

import edu.uci.ics.jung.algorithms.scoring.util.DelegateToEdgeTransformer;
import edu.uci.ics.jung.algorithms.scoring.util.VEPair;
import edu.uci.ics.jung.algorithms.util.IterativeContext;
import edu.uci.ics.jung.graph.Hypergraph;

/**
 * An abstract class for algorithms that assign scores to vertices based on
 * iterative methods. Generally, any (concrete) subclass will function by
 * creating an instance, and then either calling <code>evaluate</code> (if the
 * user wants to iterate until the algorithms is 'done') or repeatedly call
 * <code>step</code> (if the user wants to observe the values at each step).
 */
public abstract class AbstractIterativeScorer<V, E, T>
		implements IterativeContext, VertexScorer<V, T> {
	/**
	 * Maximum number of iterations to use before terminating. Defaults to 100.
	 */
	protected int max_iterations;

	/**
	 * Minimum change from one step to the next; if all changes are <=
	 * tolerance, no further updates will occur. Defaults to 0.001.
	 */
	protected double tolerance;

	/**
	 * The graph on which the calculations are to be made.
	 */
	protected Hypergraph<V, E> graph;

	/**
	 * The total number of iterations used so far.
	 */
	protected int total_iterations;

	/**
	 * The edge weights used by this algorithm.
	 */
	protected Transformer<VEPair<V, E>, ? extends Number> edge_weights;

	/**
	 * Indicates whether the output and current values are in a 'swapped' state.
	 * Intended for internal use only.
	 */
	protected boolean output_reversed;

	/**
	 * The map in which the output values are stored.
	 */
	private Map<V, T> output;

	/**
	 * The map in which the current values are stored.
	 */
	private Map<V, T> current_values;

	/**
	 * A flag representing whether this instance tolerates disconnected graphs.
	 * Instances that do not accept disconnected graphs may have unexpected
	 * behavior on disconnected graphs; they are not guaranteed to do an
	 * explicit check. Defaults to true.
	 */
	private boolean accept_disconnected_graph;

	protected boolean hyperedges_are_self_loops = false;

	/**
	 * Sets the output value for this vertex.
	 * 
	 * @param v
	 *            the vertex whose output value is to be set
	 * @param value
	 *            the value to set
	 */
	protected void setOutputValue(V v, T value) {
		output.put(v, value);
	}

	/**
	 * Gets the output value for this vertex.
	 * 
	 * @param v
	 *            the vertex whose output value is to be retrieved
	 * @return the output value for this vertex
	 */
	protected T getOutputValue(V v) {
		return output.get(v);
	}

	/**
	 * Gets the current value for this vertex
	 * 
	 * @param v
	 *            the vertex whose current value is to be retrieved
	 * @return the current value for this vertex
	 */
	protected T getCurrentValue(V v) {
		return current_values.get(v);
	}

	/**
	 * Sets the current value for this vertex.
	 * 
	 * @param v
	 *            the vertex whose current value is to be set
	 * @param value
	 *            the current value to set
	 */
	protected void setCurrentValue(V v, T value) {
		current_values.put(v, value);
	}

	/**
	 * The largest change seen so far among all vertex scores.
	 */
	protected double max_delta;

	/**
	 * Creates an instance for the specified graph and edge weights.
	 * 
	 * @param g
	 *            the graph for which the instance is to be created
	 * @param edge_weights
	 *            the edge weights for this instance
	 */
	public AbstractIterativeScorer(Hypergraph<V, E> g,
			Transformer<E, ? extends Number> edge_weights) {
		this.graph = g;
		this.max_iterations = 100;
		this.tolerance = 0.001;
		this.accept_disconnected_graph = true;
		setEdgeWeights(edge_weights);
	}

	/**
	 * Creates an instance for the specified graph <code>g</code>. NOTE: This
	 * constructor does not set the internal <code>edge_weights</code> variable.
	 * If this variable is used by the subclass which invoked this constructor,
	 * it must be initialized by that subclass.
	 * 
	 * @param g
	 *            the graph for which the instance is to be created
	 */
	public AbstractIterativeScorer(Hypergraph<V, E> g) {
		this.graph = g;
		this.max_iterations = 100;
		this.tolerance = 0.001;
		this.accept_disconnected_graph = true;
	}

	/**
	 * Initializes the internal state for this instance.
	 */
	protected void initialize() {
		this.total_iterations = 0;
		this.max_delta = Double.MIN_VALUE;
		this.output_reversed = true;
		this.current_values = new HashMap<V, T>();
		this.output = new HashMap<V, T>();
	}

	/**
	 * Steps through this scoring algorithm until a termination condition is
	 * reached.
	 */
	public void evaluate() {
		do {
			step();
		} while (!done());
	}

	/**
	 * Returns true if the total number of iterations is greater than or equal
	 * to <code>max_iterations</code> or if the maximum value change observed is
	 * less than <code>tolerance</code>.
	 */
	@Override
	public boolean done() {
		return total_iterations >= max_iterations || max_delta < tolerance;
	}

	/**
	 * Performs one step of this algorithm; updates the state (value) for each
	 * vertex.
	 */
	@Override
	public void step() {
		swapOutputForCurrent();

		for (V v : graph.getVertices()) {
			double diff = update(v);
			updateMaxDelta(v, diff);
		}
		total_iterations++;
		afterStep();
	}

	/**
	 * 
	 */
	protected void swapOutputForCurrent() {
		Map<V, T> tmp = output;
		output = current_values;
		current_values = tmp;
		output_reversed = !output_reversed;
	}

	/**
	 * Updates the value for <code>v</code>. This is the key
	 * 
	 * @param v
	 *            the vertex whose value is to be updated
	 * @return
	 */
	protected abstract double update(V v);

	protected void updateMaxDelta(V v, double diff) {
		max_delta = Math.max(max_delta, diff);
	}

	protected void afterStep() {
	}

	@Override
	public T getVertexScore(V v) {
		if (!graph.containsVertex(v)) {
			throw new IllegalArgumentException(
					"Vertex " + v + " not an element of this graph");
		}

		return output.get(v);
	}

	/**
	 * Returns the maximum number of iterations that this instance will use.
	 * 
	 * @return the maximum number of iterations that <code>evaluate</code> will
	 *         use prior to terminating
	 */
	public int getMaxIterations() {
		return max_iterations;
	}

	/**
	 * Returns the number of iterations that this instance has used so far.
	 * 
	 * @return the number of iterations that this instance has used so far
	 */
	public int getIterations() {
		return total_iterations;
	}

	/**
	 * Sets the maximum number of times that <code>evaluate</code> will call
	 * <code>step</code>.
	 * 
	 * @param max_iterations
	 *            the maximum
	 */
	public void setMaxIterations(int max_iterations) {
		this.max_iterations = max_iterations;
	}

	/**
	 * Gets the size of the largest change (difference between the current and
	 * previous values) for any vertex that can be tolerated. Once all changes
	 * are less than this value, <code>evaluate</code> will terminate.
	 * 
	 * @return the size of the largest change that evaluate() will permit
	 */
	public double getTolerance() {
		return tolerance;
	}

	/**
	 * Sets the size of the largest change (difference between the current and
	 * previous values) for any vertex that can be tolerated.
	 * 
	 * @param tolerance
	 *            the size of the largest change that evaluate() will permit
	 */
	public void setTolerance(double tolerance) {
		this.tolerance = tolerance;
	}

	/**
	 * Returns the Transformer that this instance uses to associate edge weights
	 * with each edge.
	 * 
	 * @return the Transformer that associates an edge weight with each edge
	 */
	public Transformer<VEPair<V, E>, ? extends Number> getEdgeWeights() {
		return edge_weights;
	}

	/**
	 * Sets the Transformer that this instance uses to associate edge weights
	 * with each edge
	 * 
	 * @param edge_weights
	 *            the Transformer to use to associate an edge weight with each
	 *            edge
	 * @see edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight
	 */
	public void setEdgeWeights(Transformer<E, ? extends Number> edge_weights) {
		this.edge_weights = new DelegateToEdgeTransformer<V, E>(edge_weights);
	}

	/**
	 * Gets the edge weight for <code>e</code> in the context of its (incident)
	 * vertex <code>v</code>.
	 * 
	 * @param v
	 *            the vertex incident to e as a context in which the edge weight
	 *            is to be calculated
	 * @param e
	 *            the edge whose weight is to be returned
	 * @return the edge weight for <code>e</code> in the context of its
	 *         (incident) vertex <code>v</code>
	 */
	protected Number getEdgeWeight(V v, E e) {
		return edge_weights.transform(new VEPair<V, E>(v, e));
	}

	/**
	 * Collects the 'potential' from v (its current value) if it has no outgoing
	 * edges; this can then be redistributed among the other vertices as a means
	 * of normalization.
	 * 
	 * @param v
	 */
	protected void collectDisappearingPotential(V v) {
	}

	/**
	 * Specifies whether this instance should accept vertices with no outgoing
	 * edges.
	 * 
	 * @param accept
	 *            true if this instance should accept vertices with no outgoing
	 *            edges, false otherwise
	 */
	public void acceptDisconnectedGraph(boolean accept) {
		this.accept_disconnected_graph = accept;
	}

	/**
	 * Returns true if this instance accepts vertices with no outgoing edges,
	 * and false otherwise.
	 * 
	 * @return true if this instance accepts vertices with no outgoing edges,
	 *         otherwise false
	 */
	public boolean isDisconnectedGraphOK() {
		return this.accept_disconnected_graph;
	}

	/**
	 * Specifies whether hyperedges are to be treated as self-loops. If they
	 * are, then potential will flow along a hyperedge a vertex to itself, just
	 * as it does to all other vertices incident to that hyperedge.
	 * 
	 * @param arg
	 *            if {@code true}, hyperedges are treated as self-loops
	 */
	public void setHyperedgesAreSelfLoops(boolean arg) {
		this.hyperedges_are_self_loops = arg;
	}

	/**
	 * Returns the effective number of vertices incident to this edge. If the
	 * graph is a binary relation or if hyperedges are treated as self-loops,
	 * the value returned is {@code graph.getIncidentCount(e)}; otherwise it is
	 * {@code graph.getIncidentCount(e) - 1}.
	 */
	protected int getAdjustedIncidentCount(E e) {
		return graph.getIncidentCount(e) - (hyperedges_are_self_loops ? 0 : 1);
	}
}
